package com.zzy.algorithm.sort;

import com.zzy.algorithm.model.PrintArray;

/**
 * 快速排序
 */
public class Q28_QuickSort {

    public static int[] nums = new int[]{5,7,1,2,8,9,3};

    public static void main(String[] args) {
        quickSort(nums,0,nums.length - 1);
        PrintArray.print(nums);
    }


    private static void quickSort(int[] nums,int start,int end){
        if(nums.length < 1 || start < 0 || end > nums.length - 1 || start > end){
            return;
        }
        int zoneIndex = partation(nums,start,end);
        quickSort(nums,0,zoneIndex - 1);
        quickSort(nums,zoneIndex+1,end);
    }

    private static int partation(int[] nums,int start,int end){
        if(start == end){
            return start;
        }
        int lastNum = nums[end];
        int zoneIndex = start - 1;
        for(int i = start ; i <= end;i++){
            if(nums[i] <= lastNum){
                zoneIndex++;
                if(i > zoneIndex){
                    swap(nums,i,zoneIndex);
                }
            }
        }
        return zoneIndex;
    }

    private static void swap(int[] nums,int start,int end){
        int tmp = nums[start];
        nums[start] = nums[end];
        nums[end] = tmp;
    }







//
//
//    private static int[] quickSort(int[] nums, int start, int end) {
//        if(nums.length < 1 || start < 0 || end > nums.length - 1 || start > end){
//            return null;
//        }
//        int zoneIndex = partition(nums,start,end);
//        quickSort(nums,start,zoneIndex - 1);
//        quickSort(nums,zoneIndex + 1,end);
//        return nums;
//    }
//
//    private static int partition(int[] nums, int start, int end) {
//        int lastNum = nums[end];
//        int zoneIndex = start - 1;
//        for(int i = start ; i <= end ; i++){
//            if(nums[i] <= lastNum){
//                zoneIndex++;
//                if(i > zoneIndex){
//                    swap(nums,i,zoneIndex);
//                }
//            }
//        }
//        return zoneIndex;
//    }
//
//
//    private static void swap(int[] array,int i,int j){
//        int tmp = array[i];
//        array[i] = array[j];
//        array[j] = tmp;
//    }


}
